package code;

import java.util.ArrayList;
import java.util.List;

public class Code98 {
	/*
	 * 误区，验证一个二叉树是BST，不能简单的p与它的左右儿子比较
	 * 虽然，x>y>z,=> x>z
	 * 但是，x>y,y<z,那么无法判断 x与z的关系
	 * 还是需要根据BST的定义来判断
	 * 1)	p大于左子树的所有元素，小于p的右子树的所有值
	 * 2)	先序遍历树，如果序列是拍好序的，那么就是BST
	 */
	
	//2)
	public void preOrder(TreeNode p,List<Integer> list){
		if(p==null)
			return ;
		if(p.left!=null)
			preOrder(p.left,list);
		list.add(p.val);
		if(p.right!=null)
			preOrder(p.right,list);
	}
	
    public boolean isValidBST(TreeNode root) {
        List<Integer> list=new ArrayList<Integer>();
        if(root==null)	
        	return true;
        preOrder(root,list);
        int i=0;
        for(i=1;i<list.size();i++){
        	if(list.get(i)<=list.get(i-1))
        		break;
        }
        if(i<list.size())
        	return false;
    	return true;
    }
}

